#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <map>
#include <boost/algorithm/string.hpp>

using namespace std;

#define PAGES_ESTIMATED 4000000
#define PAGES_RESIZE_STEP 1000000
#define LINKS_ESTIMATED 7000000
#define NAMESPACE_CATEGORY "Категория:"
#define MAX_DEPTH 10

enum link_type { page, file, subcat };

class CWikiDump;

struct CWikiLink {
  unsigned int from;
  unsigned int to;
  link_type type;

  std::string to_string() const {
    std::stringstream ss;
    ss << "CWikiLink " << from << " " << to << " " << type;
    return ss.str();
  }
};

class CWikiPage {
  unsigned int m_id;
  string m_title;

  std::vector<CWikiLink*> m_uplinks;

public:
  CWikiPage(unsigned int _id, const string &_title) 
    : m_id(_id), m_title(_title) { }

  inline unsigned int id() const { return m_id; }
  inline std::string title() const { return m_title; }

  virtual std::string to_string() const { return std::string("Page ") + m_title; }

  friend class CWikiDump;
};

class CWikiCategory : public CWikiPage {

  std::vector<CWikiLink*> m_downlinks;
  std::vector<CWikiLink*> m_pages;
  std::vector<CWikiLink*> m_files;
  std::vector<signed int> m_pages_count; // [0] - 1st level subcat, [1] - 2nd level subcat, ...

public:
  CWikiCategory(unsigned int _id, const string &_title)
    : CWikiPage(_id, _title) {
    m_pages_count.resize(MAX_DEPTH, -1);
  }

  virtual std::string to_string() const { return std::string("Category ") + title(); }

  friend class CWikiDump;
};

class CWikiDump {
  std::vector<CWikiPage*> m_pages;
  unsigned int m_last_page_id;
  std::map<std::string, unsigned int> m_name2id;
  std::vector<CWikiLink*> m_links;
  CWikiCategory *m_pRoot;

  void load_pages_articles(std::string fn);
  void load_category_links(std::string fn);
  void build_tree();
  CWikiCategory* find_root();
  void calc_pages_count();
  void calc_pages_count(unsigned int id, unsigned int depth);

public:
  std::string to_string_1() const;

public:
  CWikiDump(std::string fn_cl, std::string fn_pa)
    : m_pRoot(NULL), m_last_page_id(0) {
    m_pages.resize(PAGES_ESTIMATED, NULL);
    m_links.resize(LINKS_ESTIMATED, NULL);
    load_pages_articles(fn_pa);
    load_category_links(fn_cl);
    build_tree();
    if (NULL == (m_pRoot = find_root())) {
      cerr << "can't find root category" << endl;
      throw;
    }
    cout << "root category is \"" << m_pRoot->to_string() << "\"" << endl;
    calc_pages_count();
  }

};

CWikiDump dump("/home/lazyfrog-nb-ubuntu/my/kwscripts/wiki/20120213-categorylinks.txt",
//               "/home/lazyfrog-nb-ubuntu/my/kwscripts/wiki/20120213-pagesarticles.txt");
               "/home/lazyfrog-nb-ubuntu/my/kwscripts/wiki/20120213-pagesmeta.txt");

int main(int argc, char** argv) {

  cout << dump.to_string_1();

  return 0;
}

CWikiCategory* CWikiDump::find_root() {
  std::vector<CWikiPage*>::const_iterator cit = m_pages.begin();
  while (m_pages.end() != cit) {
    CWikiCategory *p_cat = NULL;

    if (NULL != *cit && NULL != (p_cat = dynamic_cast<CWikiCategory*>(*cit))) {
      if (0 == p_cat->m_uplinks.size() && p_cat->m_downlinks.size() > 0)
        return p_cat;
    }

    cit++;
  }

  return NULL;
}

void CWikiDump::calc_pages_count() {
  cerr << "-> calc_pages_count" << endl;

  std::vector<CWikiPage*>::const_iterator cit = m_pages.begin();
  while (m_pages.end() != cit) {
    CWikiCategory *p_cat = NULL;

    if (NULL != *cit && NULL != (p_cat = dynamic_cast<CWikiCategory*>(*cit))) {
      for (int i = 0; i < MAX_DEPTH; i++) {
        calc_pages_count(p_cat->id(), i);
      }
    }

    cit++;
  }

  cerr << "<- calc_pages_count" << endl;
}

void CWikiDump::calc_pages_count(unsigned int id, unsigned int depth) {
  cerr << "-> calc_pages_count(" << id << ", " << depth << ")" << endl;

  CWikiCategory *p_cat = dynamic_cast<CWikiCategory*>(m_pages[id]);
  unsigned int c = 0;    

  if (NULL != p_cat) {
 
    std::vector<CWikiLink*>::iterator it = p_cat->m_downlinks.begin();
    while (p_cat->m_downlinks.end() != it) {
      CWikiCategory *pc = dynamic_cast<CWikiCategory*>(m_pages[(*it)->to]);
      if (NULL == pc) {
        cerr << (*it)->to << " isn't a category" << endl;
        throw;
      }
      c += pc->m_pages.size();

      for (int i = 0; i < depth; i++) {
        if (-1 == pc->m_pages_count[i])
          calc_pages_count(pc->id(), depth - 1);
        c += pc->m_pages_count[i];
      } 
 
      it++;
    }

    p_cat->m_pages_count[depth] = c;
  } else {
    cerr << id << " isn't a category" << endl;
    throw;
  }
 
  cerr << "<- calc_pages_count(" << id << ", " << depth << ") == " << c << endl;
}

void CWikiDump::build_tree() {
  cerr << "-> build_tree" << endl;
  vector<CWikiLink*>::const_iterator cit = m_links.begin();
  unsigned int wrong = 0;
  while (m_links.end() != cit) {
    if (NULL == *cit) {
      cit++;
      continue;
    }
    cerr << (*cit)->to_string() << endl;
    CWikiLink *pl = *cit;
    if (NULL == m_pages[pl->from] || NULL == m_pages[pl->to]) {
      cerr << "wrong from/to in catlink from " << pl->from << " to " << pl->to << endl;
      wrong++;
//      throw;
      cit++;
      continue;
    }
    m_pages[pl->from]->m_uplinks.push_back(pl);
    CWikiCategory *p_cat = dynamic_cast<CWikiCategory*>(m_pages[pl->to]);
    if (NULL == p_cat) {
      cerr << pl->to << " isn't a category." << endl;
      throw;
    }

    switch (pl->type) {
      case subcat:
        p_cat->m_downlinks.push_back(pl);
        break;

      case page:
        p_cat->m_pages.push_back(pl);
        break;

      case file:
        p_cat->m_files.push_back(pl);
        break;

      default:
        cerr << "wrong type value in catlink from " << pl->from << " to " << pl->to << endl;
        throw;
    }

    cit++;
  }

  cerr << "total wrong: " << wrong << endl;
  cerr << "<- build_tree" << endl;
}

std::string CWikiDump::to_string_1() const {
  cerr << "-> to_string_1" << endl;
  vector<CWikiPage*>::const_iterator cit = m_pages.begin();
  std::stringstream ss;

  while (m_pages.end() != cit) {
    if (NULL == *cit) {
      cit++;
      continue;
    }
    CWikiCategory *p_cat = dynamic_cast<CWikiCategory*>(*cit);
    if (NULL == p_cat) {
      cit++;
      continue;
    }
    
    ss << p_cat->id() << " ";
    ss << p_cat->to_string() << " " << p_cat->m_uplinks.size() << " ";
    ss << p_cat->m_downlinks.size() << " " << p_cat->m_pages.size() << " ";
    ss << p_cat->m_files.size();

    ss << " | ";
    for (int i = 0; i < MAX_DEPTH; i++)
      ss << p_cat->m_pages_count[i] << " ";

    ss << endl;

    cit++;
  }
  cerr << "<- to_string_1" << endl;
  return ss.str();
}

void CWikiDump::load_pages_articles(std::string fn) {
  std::ifstream f(fn.c_str());
  if (!f.is_open()) throw;
  std::string s;
  while (getline(f, s)) {
    std::vector<std::string> v;
    boost::split(v, s, boost::is_any_of("\t"));
    if (v.size() < 3) {
      cerr << "can't parse string \"" << s << "\"" << endl;
      continue;
    }
    unsigned int id = atoi(v[0].c_str());
    if (v[1].substr(0, strlen(NAMESPACE_CATEGORY)) == NAMESPACE_CATEGORY) {
      m_pages[id] = new CWikiCategory(id, v[1]);
//      cerr << v[1] << " is a category" << endl;
    } else {
      m_pages[id] = new CWikiPage(id, v[1]); 
//      cerr << v[1] << " is a page" << endl;
    }
    m_name2id[v[1]] = id;
    m_last_page_id = id;
  }
  cerr << m_pages.size() << " pages in vector" << endl;
  cerr << m_name2id.size() << " names in map" << endl;
}

void CWikiDump::load_category_links(std::string fn) {
  std::ifstream f(fn.c_str());
  if (!f.is_open()) throw;
  std::string s;
  unsigned int i = 0;
  unsigned int last_page_id = m_last_page_id;

  while (getline(f, s)) {
    std::vector<std::string> v;
    boost::split(v, s, boost::is_any_of("\t"));
    if (v.size() < 7) {
      cerr << "can't parse string \"" << s << "\"" << endl;
      continue;
    }
    m_links[i] = new CWikiLink();
    m_links[i]->from = atoi(v[0].c_str());
    std::string cat_name = "Категория:" + v[1];
    map<std::string, unsigned int>::const_iterator cit = m_name2id.find(cat_name);
    if (m_name2id.end() == cit) {
//      cerr << "name \"" << cat_name << "\" not found in m_name2id" << endl;
      last_page_id += 1;
      if (m_pages.size() <= last_page_id) 
        m_pages.resize(m_pages.size() + PAGES_RESIZE_STEP);
      m_pages[last_page_id] = new CWikiCategory(last_page_id, cat_name);
      m_name2id[cat_name] = last_page_id;
      cit = m_name2id.find(cat_name);
      //throw;
    }
    m_links[i]->to = cit->second;
    if ("subcat" == v[6]) 
      m_links[i]->type = subcat;
    else if ("page" == v[6])
      m_links[i]->type = page;
    else if ("file" == v[6])
      m_links[i]->type = file;
    else {
      cerr << "unknown value \"" << v[6] << "\" in line \"" << s << "\"" << endl;
      throw;
    }
     
    ++i;
  }
  cerr << m_links.size() << " links in vector" << endl;
}


